/**
 * 
 */
package linkedlist.passed;

/**
 * @author xyyi
 *
 */
public class RemoveDuplicatesFromSortedListII {

	/**
	Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

	For example,
	Given 1->2->3->3->4->4->5, return 1->2->5.
	Given 1->1->1->2->3, return 2->3.
	 */
	public ListNode deleteDuplicates(ListNode head) {
		if (head == null)
			return head;

		ListNode dummyNode = new ListNode(-1);
		dummyNode.next = head;
		head = dummyNode;
		//pitfall, need to check head, head.next and head.next.next for null
		while (head != null && head.next != null && head.next.next != null) {
			ListNode next = head.next.next;
			while (next != null && head.next.val == next.val) {
				next = next.next;
			}
			if (head.next.next != next) {
				// romve the duplicated node and do not need move head again
				head.next = next;
			} else {
				// head move forward for no nodes removed
				head = head.next;
			}
		}

		return dummyNode.next;
	}

	/**
	 * Definition for singly-linked list.
	 */
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}

	/**
	 * 
	 */
	public RemoveDuplicatesFromSortedListII() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
